//
// Created by user on 2022/1/12.
//

#include <iostream>
#include <vector>

using namespace std;

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        int index = abs(nums[i])-1;
        if(nums[index]<0){res.push_back(abs(nums[i]));}
        nums[index] = -nums[index];
    }
    return res;
}

vector<int> findDuplicates2(vector<int>&nums){
    vector<int> res;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int index = (nums[i]-1)%n;
        nums[index]+=n;
    }
    for (int i = 0; i < n; ++i) {
        if(nums[i]>2*n){
            res.push_back(i+1);
        }
    }
    return res;
}
int main() {

//   std::cout << "Hello, World!" << std::endl;
    vector<int> nums= {4,3,2,7,8,2,3,1};
    vector<int> res= findDuplicates2(nums);
    std::cout << res.at(1) << std::endl;

    return 0;
}